Menurut penduduk Tambisan, nama Tambisan diperoleh daripada dua cerita atau versi yang saling berkaitan. Versi pertama adalah, semasa Panglima Tumikbi (Adalah Peneroka terawal) membersihkan pulau Tambisan, mereka menemui pohon yang lebat buahnya. Orang Melayu mengelar pohon tersebut sebagai Jambu Air Mawar dan orang Suluk mengelar Tambis. Manakala bagi versi kedua. pula, nama Tambisan ini adalah berasal daripada seorang lelaki bernama Tambi dan seorang wanita bernama San. Apabila mereka berkahwin, maka muncul la nama Tambisan. Namun Imam Mansor versi yang diceritakan oleh beliau sedikit berbeza dengan Encik Hassan. Menurut beliau, ada seorang bangsa Tambi (India) datang menjual kain di Tambisan.

Semasa Panglima Tumikbi memohon tanah di pejabat daerah di Lahad Datu, Rasdin Muji selaku Ketua Pejabat Daerah ketika bertanyakan nama pulau tersebut. Panglima Tumikbi meletakkan nama pulau tersebut sebagai Tambisan dengan mengabungkan dua versi cerita tersebut.